package leetcode_100;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *BinaryTreeInorderTraversal_94 先序遍历二叉树
 *describe:递归遍历AC 98% 栈非递归遍历 AC 44%
 *2018年5月18日 下午9:42:54
 */
public class BinaryTreeInorderTraversal_94 {
	static class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}
	List<Integer> res;
	public static void main(String[] args) {
		BinaryTreeInorderTraversal_94 test=new BinaryTreeInorderTraversal_94();
		TreeNode a=new TreeNode(1);
		a.left=new TreeNode(2);
		a.right=new TreeNode(3);
		a.right.left=new TreeNode(4);
		a.right.right=new TreeNode(5);
		test.inorderTraversal(a);
	}
	
	/**
	 * describe:非递归先序遍历二叉树  加入栈数据结构 
	 * 2018年5月18日 下午9:42:29
	 */
	public List<Integer> inorderTraversal(TreeNode root) {
		this.res=new ArrayList<Integer>();
		List<TreeNode> nodes=new ArrayList<TreeNode>();//当栈使用
		int count=1;
		TreeNode now;
		if(root==null)
			return res;
		else {
			nodes.add(root);
			now=root.left;
			while(now!=null||count!=0) {
				if(now!=null) {
					nodes.add(now);
					++count;
					now=now.left;
				}
				else {
					TreeNode node=nodes.get(count-1);
					this.res.add(node.val);
					nodes.remove(node);
					--count;
					now=node.right;
				}
			}
		}
        return this.res;
    }
	
	public void travel(TreeNode root) {
		if(root!=null) {
			travel(root.left);
			this.res.add(root.val);
			travel(root.right);
		}
	}

}
